package leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

/**
 * Created by Ghost on 2014/12/24 0024.
 */
public class Max_Points_on_a_Line {
    public int maxPoints(Point[] points) {
        if(points.length<2)
            return points.length;
        int max = 0;
        int dumplicated = 0;
        int Bigest = 0;
        HashMap<Float, Integer> map = new HashMap<Float, Integer>();
        for(int i=0;i<points.length;i++){
            map.clear();
            dumplicated = 0;
            Bigest=0;
            for(int j=0;j<points.length;j++){
                if(i==j){
                    dumplicated++;
                    continue;
                }
                else{
                    if(points[i].x==points[j].x && points[i].y==points[j].y){
                        dumplicated++;
                    }
                    else if(points[i].x==points[j].x && points[i].y!=points[j].y){
                        Bigest++;
                    }
                    else{
                        float k = (float)(points[i].y-points[j].y)/(float)(points[i].x-points[j].x);
                        if(map.containsKey(k))
                            map.put(k,map.get(k)+1);
                        else
                            map.put(k,1);
                    }
                }
            }

            Set<Map.Entry<Float,Integer>> entrySet = map.entrySet();
            max = max>(Bigest+dumplicated)?max:(Bigest+dumplicated);
            for(Map.Entry<Float,Integer> entry1:entrySet){
                max = max<(entry1.getValue()+dumplicated)?(entry1.getValue()+dumplicated):max;
            }

        }
        return max;
    }

    public static void main(String[] args){
        Max_Points_on_a_Line max_points_on_a_line = new Max_Points_on_a_Line();
        ArrayList<Point> pointArrayList = new ArrayList<Point>();
        pointArrayList.add(new Point(1,1));
        pointArrayList.add(new Point(1,1));
        /*pointArrayList.add(new Point(3,3));
        pointArrayList.add(new Point(2,1));
        pointArrayList.add(new Point(3,1));
        pointArrayList.add(new Point(1,3));
        pointArrayList.add(new Point(1,4));
        pointArrayList.add(new Point(8,8));*/
        Point[] points = pointArrayList.toArray(new Point[2]);
        System.out.println(max_points_on_a_line.maxPoints(points));
    }
}
